impl Solution {
    pub fn get_maximum_generated(n: i32) -> i32 {
        if n==0{
            return 0
        }
        if n==1{
            return 1
        }
        let mut bp =vec!(0;(n+1) as usize);
        let mut ans=0;
        for i in 2..n+1{
            ans=ans.max(Solution::bp_dfs(i as usize,&mut bp))
        }
        ans
    }
    fn bp_dfs(i :usize,bp:&mut[i32])->i32{
        if i==0{
            return 0
        }else if i==1{
            return 1
        }

        if bp[i]==0{
            if i%2==0{
                bp[i]=Solution::bp_dfs(i/2,bp)

            }else{
                bp[i]=Solution::bp_dfs(i/2,bp)+Solution::bp_dfs(i/2+1,bp)
            }
        }
        bp[i]
    }
}